package com.kobe.algorithm.leetcode.daytest.day1;

public class Case704_dichotomy {


    public static int search(int[] nums, int target) {
//        return search(nums,target,0,nums.length-1);
        if(nums.length == 0 || target> nums[nums.length-1]){
            return -1;
        }

        int left = 0,right = nums.length - 1;
        while(left <= right){
            int middle = left + ((right-left)/2==0 ?(right-left)/2 : (right-left)/2+1);
            if(nums[middle]  == target){
                return middle;
            }else if(nums[middle] >target){
                right = middle -1;
            }else if(nums[middle] < target){
                left = middle + 1;
            }
        }
        return -1;
    }


    private static int search(int[] nums,int target,int startIndex,int endIndex ){

        int indexAdd = (endIndex-startIndex)%2 == 0?(endIndex-startIndex)/2 : (endIndex-startIndex)/2+1;
        if(indexAdd  <= 1){
            if(nums[startIndex] == target){
                return startIndex;
            }else if(nums[startIndex+indexAdd] == target){
                return startIndex+indexAdd;
            }else if(nums[endIndex] == target){
                return endIndex;
            }else{
                return -1;
            }
        }
        int index  = startIndex+indexAdd;
        if(nums[index] > target){
            return search(nums,target,startIndex,index);
        }else if(nums[index] < target){
            return search(nums,target,index,endIndex);
        }else{
            return index;
        }
    }

    public static void main(String[] args) {
        int nums[] = {1,2,3,4,7,90,321,2323,1212112};

        int index = search(nums,2323);
        System.out.println(index);
    }

}
